/*
 *  Copyright 2009 Advanced Industrial Science and Technology (AIST).
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/*! \file
 *  \brief
 */
#pragma once

// thrust, includes
#include <thrust/for_each.h>
#include <thrust/sort.h>
#include <thrust/copy.h>
#include <thrust/reduce.h>
#include <thrust/sequence.h>
#include <thrust/functional.h>

#include <thrust/reduce_by_keyvalue.hpp>

// stl, includes
#include <iostream>

namespace thrust {

namespace detail {

  template <typename Edge, typename Vertex>
  struct copy_source_vertex : public unary_function<Edge,Vertex>
  {
    __device__
    inline Vertex
    operator()( Edge& e){
      return e.m_source;
    }
  };
  
  template <typename Edge, typename Vertex>
  struct copy_target_vertex : public unary_function<Edge,Vertex>
  {
    __device__  
    inline Vertex
    operator()( Edge& e){
      return e.m_target;
    }
  };
  
  struct re_out_edges_op
  {
    template <typename Tuple>
    __device__
    void operator()( Tuple t){
      size_t head =thrust::get<1>(t);
      size_t tail =thrust::get<2>(t);
      
      if( head <=tail)
        thrust::get<0>(t).set_out_edges( head, tail + 1);
      else
        thrust::get<0>(t).set_out_edges( thrust::numeric_limits<size_t>::max(),
                                         thrust::numeric_limits<size_t>::max());
    }
  };
  
  struct re_in_edges_op
  {
    template <typename Tuple>
    __device__
    void operator()( Tuple t){
      size_t head =thrust::get<1>(t);
      size_t tail =thrust::get<2>(t);
      
      if( head <=tail)
        thrust::get<0>(t).set_in_edges( head, tail + 1);
      else
        thrust::get<0>(t).set_in_edges( thrust::numeric_limits<size_t>::max(),
                                        thrust::numeric_limits<size_t>::max());
    }
  };
  
  template <typename Config, typename DirectedHelper>
  inline void
  reconstruct_out_edges( adj_list_helper<Config,DirectedHelper>& g_
                         , typename Config::vertices_size_type V
                         , typename Config::edges_size_type    E)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::EdgeContainer         EdgeContainer;
    typedef typename Config::EdgePropertyContainer EdgePropertyContainer;
    
    typedef typename graph_traits<Graph>::edge_iterator      edge_iterator;
    typedef typename graph_traits<Graph>::edge_descriptor    edge_descriptor;
    typedef typename graph_traits<Graph>::edge_property_type edge_property_type;

    Graph& g =static_cast<Graph&>(g_);
    
    device_vector<size_t> source( E);
    device_vector<size_t> indices( E);
    device_vector<size_t> key( V);
    device_vector<size_t> value( V);
    device_vector<size_t> head( V);
    device_vector<size_t> tail( V);
    
    device_vector<size_t>::iterator key_end, value_end;
    thrust::equal_to<size_t> equal_pred;
    thrust::minimum<size_t> minimum_op; 
    thrust::maximum<size_t> maximum_op;
    
    const std::size_t BLOCK_SIZE =512; // number of threads per block
    const std::size_t MAX_BLOCKS =thrust::detail::device::cuda::arch::max_active_threads() / BLOCK_SIZE;
    const std::size_t NUM_BLOCKS =std::min( MAX_BLOCKS, V + (BLOCK_SIZE - 1) / BLOCK_SIZE);
    
    thrust::transform( g.m_out_edges.begin(), 
                       g.m_out_edges.end(), 
                       source.begin(), 
                       copy_source_vertex<edge_descriptor,size_t>());
    thrust::sequence( indices.begin(), indices.end());
    
    // get head point
    tie( key_end, value_end)
      =thrust::reduce_by_key( source.begin(), source.end(), 
                              indices.begin(),
                              key.begin(),
                              value.begin(),
                              equal_pred,
                              minimum_op);
    thrust::fill( head.begin(), head.end(), std::numeric_limits<size_t>::max());
    thrust::reduce_by_keyvalue( key.begin(), key_end,
                                value.begin(),
                                head.begin(), head.end());
    
    // get tail point
    tie( key_end, value_end)
      =thrust::reduce_by_key( source.begin(), source.end(), 
                              indices.begin(),
                              key.begin(),
                              value.begin(),
                              equal_pred,
                              maximum_op);
    
    thrust::reduce_by_keyvalue( key.begin(), key_end,
                                value.begin(),
                                tail.begin(), tail.end());
    
    thrust::detail::device::for_each( thrust::make_zip_iterator( thrust::make_tuple( g.m_vertices.begin(),
                                                                                     head.begin(),
                                                                                     tail.begin())),
                                      thrust::make_zip_iterator(thrust::make_tuple( g.m_vertices.end(),
                                                                                    head.end(),
                                                                                    tail.end())),
                                      re_out_edges_op());
    
    g.ptr_out_edges =thrust::device_pointer_cast<edge_descriptor>( &g.m_out_edges[0]);
  }
  
  template <typename Config, typename DirectedHelper>
  inline void
  reconstruct_in_edges( adj_list_helper<Config,DirectedHelper>& g_
                        , typename Config::vertices_size_type V
                        , typename Config::edges_size_type    E)
  {
    typedef typename Config::graph_type Graph;
    typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    
    Graph& g =static_cast<Graph&>(g_);
    
    device_vector<size_t> source( E);
    device_vector<size_t> indices( E);
    device_vector<size_t> key( V);
    device_vector<size_t> value( V);
    device_vector<size_t> head( V);
    device_vector<size_t> tail( V);
    
    device_vector<size_t>::iterator key_end, value_end;
    thrust::equal_to<size_t> equal_pred;
    thrust::minimum<size_t> minimum_op; 
    thrust::maximum<size_t> maximum_op;
    
    const std::size_t BLOCK_SIZE =512; // number of threads per block
    const std::size_t MAX_BLOCKS =thrust::detail::device::cuda::arch::max_active_threads() / BLOCK_SIZE;
    const std::size_t NUM_BLOCKS =std::min( MAX_BLOCKS, V + (BLOCK_SIZE - 1) / BLOCK_SIZE);

    if( g.m_in_edges.size() <E){
      g.m_in_edges.resize( E);
      g.m_capacity_in_edges =E;
    }
    g.m_num_in_edges =E;
    
    thrust::copy( g.m_out_edges.begin(),
                  g.m_out_edges.end(),
                  g.m_in_edges.begin());

    thrust::sort( g.m_in_edges.begin(), 
                  g.m_in_edges.end(), 
                  thrust::detail::less_edge_target<edge_descriptor>());
    
    thrust::transform( g.m_in_edges.begin(), 
                       g.m_in_edges.end(), 
                       source.begin(), 
                       copy_target_vertex<edge_descriptor,size_t>());
    thrust::sequence( indices.begin(), indices.end());
    
    // get head point
    tie( key_end, value_end)
      =thrust::reduce_by_key( source.begin(), source.end(), 
                              indices.begin(),
                              key.begin(),
                              value.begin(),
                              equal_pred,
                              minimum_op);
    
    thrust::fill( head.begin(), head.end(), std::numeric_limits<size_t>::max());
    thrust::reduce_by_keyvalue( key.begin(), key_end,
                                value.begin(),
                                head.begin(), head.end());
    
    // get tail point
    tie( key_end, value_end)
      =thrust::reduce_by_key( source.begin(), source.end(), 
                              indices.begin(),
                              key.begin(),
                              value.begin(),
                              equal_pred,
                              maximum_op);
    
    thrust::reduce_by_keyvalue( key.begin(), key_end,
                                value.begin(),
                                tail.begin(), tail.end());
    
    thrust::detail::device::for_each( thrust::make_zip_iterator( thrust::make_tuple( g.m_vertices.begin(),
                                                                                     head.begin(),
                                                                                     tail.begin())),
                                      thrust::make_zip_iterator(thrust::make_tuple( g.m_vertices.end(),
                                                                                    head.end(),
                                                                                    tail.end())),
                                      re_in_edges_op());
    
    g.ptr_in_edges =thrust::device_pointer_cast<edge_descriptor>( &g.m_in_edges[0]);
  }
  
  
  /*template <typename Config>
  inline void
  reconstruct_in_edges( undirected_graph_helper<Config>& g_
			, typename Config::vertices_size_type V
			, typename Config::edges_size_type    E)
  {
    typedef typename Config::graph_type Graph;
    
    Graph& g =static_cast<Graph&>(g_);
    detail::reconstruct_in_edges( g, V, E);
    g.m_num_in_edges =E;
  }
  
  template <typename Config>
  inline void
  reconstruct_in_edges( bidirectional_graph_helper<Config>& g_
			, typename Config::vertices_size_type V
			, typename Config::edges_size_type    E)
  {
    std::cout <<"reconstruct_in_edges(bidirectional_hraph_helper)" <<std::endl;

    typedef typename Config::graph_type Graph;
    
    Graph& g =static_cast<Graph&>(g_);
    reconstruct_in_edges( g, V, E);
    g.m_num_in_edges =E;
    }*/
    
  template <typename Config>
  inline void
  reconstruct( directed_graph_helper<Config>& g_
               , typename Config::vertices_size_type V
               , typename Config::edges_size_type    E)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    
    reconstruct_out_edges( g, V, E);
  }

  template <typename Config>
  inline void
  reconstruct( undirected_graph_helper<Config>& g_
               , typename Config::vertices_size_type V
               , typename Config::edges_size_type    E)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    
    reconstruct_out_edges( g, V, E);
    reconstruct_in_edges( g, V, E);
  }
  
  template <typename Config>
  inline void
  reconstruct( bidirectional_graph_helper<Config>& g_
               , typename Config::vertices_size_type V
               , typename Config::edges_size_type    E)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    
    reconstruct_out_edges( g, V, E);
    reconstruct_in_edges( g, V, E);
  }

} // end namespace detail

} // end namespace thrust
